#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#define FOR(i,a,n) for(int i=a;i<n;++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
const int mod = 1000000000;
class BinaryIndexedTree
{
public:
    int *a;
    int length;
    BinaryIndexedTree(int n=20000)
    {
        a = new int[(length=n)+10];
        fill(a,a+length+10,0);
    }
    ~BinaryIndexedTree(){delete(a);}
    inline int LowBit(int pos){return pos&(-pos);}
    void Insert(int pos,int val)
    {
        while(pos<=length)
        {
            a[pos]+=val;
            if(a[pos]>=mod) a[pos]-=mod;
            pos += LowBit(pos);
        }
        //printf("query=%d\n",Query(1,length));
    }
    int Query(int lb,int rb)
    {
        if(lb!=1)
        {
            int t=Query(1,rb)-Query(1,lb-1);
            if(t<0) t+=mod;
            return t;
        }
        else
        {
            int ans = 0;
            while(rb>0)
            {
                ans+=a[rb],rb-=LowBit(rb);
                if(ans>=mod) ans-=mod;
            }
            return ans;
        }
    }
};

int a[20020];
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        BinaryIndexedTree bitTree[12];
        REP(i,n) scanf("%d",a+i);
        REP(i,n)
        {
            FOR(j,1,k+1)
            {
                int t = j==1?1:bitTree[j-1].Query(a[i]+1,n);
                bitTree[j].Insert(a[i],t);
            }
        }
        int ans = bitTree[k].Query(1,n);
        cout<<ans<<endl;
    }
	return 0;
}
